package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

/**
 * 解开密码锁问题
 */
public class Solution2 {
    private int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>();
        for (String s : deadends) {
            deadSet.add(s);
        }
        if (deadSet.contains(target) || deadSet.contains("0000")) {
            return -1;
        }
        if (target.equals("0000")) {
            return 0;
        }
        //BFS
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> visited = new HashMap<>();
        queue.add("0000");
        visited.put("0000", 0);
        while (!queue.isEmpty()) {
            String curs = queue.remove();
            char[] curarray = curs.toCharArray();
            List<String> nexts = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                char o = curarray[i];
                curarray[i] = Character.forDigit((curarray[i] - '0' + 1) % 10, 10);
                nexts.add(new String(curarray));
                curarray[i] = o;
                curarray[i] = Character.forDigit((curarray[i] - '0' + 9) % 10, 10);
                nexts.add(new String(curarray));
                curarray[i] = o;
            }
            for (String next : nexts) {
                if (!deadSet.contains(next)
                        && !visited.containsKey(next)) {
                    queue.add(next);
                    visited.put(next, visited.get(curs) + 1);
                    if (next.equals(target)) {
                        return visited.get(next);
                    }
                }
            }
        }
        return -1;
    }

}
